COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.SEC(Projects)
C00009 00003	.SS(A project: Syntax-directed processes,syntax-directed)
C00010 00004	.SS(%3evalquote%*,%3evalquote%*)
C00018 ENDMK
C⊗;
.SEC(Projects)
*********write intro *********
.SS(A project: extensions to %3eval%*,%3eval%*,P67:)
.SELECT 1;


.BEGIN TURN ON "#";
This next extension to %3eval%*  was derived from the syntax of ⊗→MUDDLE↔←, ⊗→CONNIVER↔←, and
⊗→MICRO-PLANNER↔←.
We have seen that LISP calling sequences are of two varieties: functions calls,
evaluating %2all%* of the arguments; and special forms, evaluating %2none%* of the
arguments.

In an attempt to generalize this regime we might allow the evaluation of some
of the arguments and enlarge on the domain
of objects which can appear in the list of λ-variables.
We might partition the formal parameters into obligatory parameters, optional 
parameters, and an excess collector.
Obligatory parameters %2must%* have corresponding actual parameters; optional
actual parameters are used if present, otherwise declared default 
values are used; and
if there are more actual parameters than the formals encompassed by the first
two classes, then they are associated with the excess collector.

To be more precise consider the following possible BNF equations:

.BEGIN TABIT1(13);TURN OFF "←";

<varlist>\::=[<obligatory> <optional> <excess>]

<obligatory>\::= <par>; ...<par> | %cε%*

<optional>\::= "optional" <opn>; ... <opn> | %cε%*

<excess>\::= "excess" <par> | %cε%*

<par>\::= <variable> | @<variable>

<opn>\::= <par> | <par> ← <form>

.END
The associated semantics follows:

.BEGIN INDENT 0,10;TURN OFF "←";
%21.%*  The formal parameters are to be bound to the actual parameters from
left to right (as usual).

%22.%*  There must be an actual parameter for each obligatory parameter, and
if there is no excess collector there may not be more actual parameters than
formals. (There may be less if we have optionals.)

%23.%*  If a <variable> in a formal parameter is preceeded by a "@", then
the corresponding actual parameter is %2not%* evaluated.

%24.%*  We might run out of actual parameters while binding the optionals.
If we do, then we look at the remaining formal optionals.
If a formal is simply a <par> then bind it to %3NIL%*; if a formal is
@<variable> ← <form> then bind the <variable> to the <form>; or if the formal is
<variable> ← <form>, bind <variable> to the value of <form>.

%25.%*  Finally, the excess collector is bound to a list of any remaining
actual parameters in the obvious way: if <par> is <variable> then form a list
of the values of the remainder; if it is @<variable>, bind <variable> to the
actual list. If there is no excess, bind to %3NIL%*.
.END

.BEGIN TURN OFF "←";
These same languages have extended %3prog%*-variables slightly, allowing 
them to be initialized explicitly. If a %3prog%*-variable is atomic,
intialize it to %3NIL%*, as usual. If it is of the form <variable>#←#<form>
then initialize it to the value of the <form>.
.END
.END

.BEGIN TURN OFF "←";turn on "\"; tabs 10,20;
Here are some examples:

1. In the initialization of %3length%* on {yon(P45)}, we could write:
%3...#prog[[l#←#x;#c#←#0]#....%*

2. %3list%* could now be defined as: %3λ[[%1"excess"%* x]x]%*.

3. Consider the following definition:
.BEGIN NOFILL;
.group

\%3baz <= λ[\[x;%1@%*y;%1"optional"%* z; u ← 0; %1"excess"%* v]
\\print[x];
\\print[y];
\\print[z];
\\print[u];
\\print[v]].
.APART
%1Then a call of:
%3eval[(BAZ 2 (CAR (QUOTE (X Y)) 4 5 6 7 (CAR (QUOTE (A . B))));NIL]%* would print:

%3 
2  
(CAR(QUOTE (X Y)) 
4
5 
(6 7 A)%*
(and return value: %3(6 7 A)%*.

Similarly defining;

.GROUP
\%3fii <= λ[\[x;y;%1"optional"%* z; u ← 0; %1"excess"%3 v]
\\print[x];
\\print[y];
\\print[z];
\\print[u];
\\print[v]].

%1and calling:
%3eval[(FII 2 (CAR (QUOTE (X Y)));NIL]%* prints:
%3 
2 
X 
NIL 
0 
NIL.%*
.END
.END

←%2Problems%*

Design simple sexpr representations of these proposed constructs.
Make these extensions to %3eval%*.  How useful are these syntactic
sugarings?


.SS(A project: Syntax-directed processes,syntax-directed)
%1
.REQUIRE "NOTES.SDP" SOURCE_FILE;
.SS(%3evalquote%*,%3evalquote%*)
The basic structure of the  %3evalquote%*-loop is:

%21.%*  read in a (Sexpr representation of) function . I.e., a name
	or a lambda expression.

%22.%*  read in a list of (evaluated) arguments to be applied to the function.

%23.%*  apply the function (of step %21.%*) to the argument list.

%24.%*  print the value.

%25.%*  go to step %21.%*

Thus the structure of the loop  is essentially:

.BEGIN TABIT2(24,27);TURN OFF "←";
%3
.GROUP
                   prog[[fn;x;z]
\l\fn ← read[ ];
\\x ← read[ ];
\\z ← evalquote[fn;x];
\\print[z];
\\go[l]]]

%1where: %3evalquote <= λ[[fn;x]apply[fn;x;NIL]]
.APART
%*

or more concisely:

%3
.GROUP
\prog[[ ]
\ l    print[evalquote[read[ ];read[ ]]];
\      go[l]]
.APART

%*
.END
.GROUP
where:

%21.%*  the function, ⊗→%3read%*↔←, negotiates with an input device to read an
Sexpression.

%22.%*  the function, ⊗→%3print%*↔←, prints the value of its argument on an output
device.
.APART

The details of %3read%* and %3print%* will appear when we discuss implementation
of LISP.

.BEGIN TURN ON "#";
Here's an example of the behavior of %3evalquote%*. Assume that the input
device contains %2CAR#((A#B))%*. Then the first %3read%* in %3evalquote%* gets
%2CAR%* (a string representing an Sexpr), and the second read gets %2((A#B))%*; 
then %3apply%* gets called as:
%3

←apply[CAR;((A B));NIL].
%*

%3apply%* says that this is the same as evaluating
%3car[(A#B)]%*, and thus returns %3A%* as its answer, which is dutifully
printed by %3print%*.  
.END

So %3evalquote%* can be used as a `desk calculator' for LISP. 
If we wish to evaluate an expression %3f[a%41%*;#...#a%4n%*]%1 for
%3a%4i%1 constants, i.e. sexprs, then %3evalquote[F;#(a%41%*#...#a%4n%*)]%1
will do it for us.  But the %3evalquote%*-loop will %2not%* evaluate arguments;
the a%4i%1's in the call on %3evalquote%* are not expressions, not translates
of constants, but are constants.
Typing %2CONS#((CAR#(QUOTE#(A)))#(QUOTE#(B)))%* to the %3evalquote%*-loop
will result in %3((CAR#(QUOTE#(A)))#.#(QUOTE#(B)))%*.

The %3evalquote%*-loop is an anomaly. It does not expect the usual representation
of a LISP form say %3(F e%41%* ... e%4n%*)%1  where the %3e%4i%1's 
are to be evaluated. It expects a %2pair%* of sexprs representing a function
and %2evaluated%* arguments. The benefits of having "functional-notation" as
input and having arguments implicitly evaluated are greatly outweighed
by the confusion introduced by having two formats for LISP expressions, one for
the "top-level" and a different one everywhere else.


Certainly
before we can do any reasonable amount of calculation, we must be 
able to define and name our own functions. The %3label%* operator, or
 calling %3eval%* with an intial symbol table containing
our definitions will suffice, but this is not particularly elegant.
We would like our definitions to have some permanence.

A function (actually a %2special form%*, if you have been paying attention)
named ⊗→%3define%*↔←, whose effect is to add definitions to %3apply%*, has been 
provided. The actual behavior of %3define%* will appear in the sections on
implementation.

.P51:
%3define%* is the name of a special form (its arguments are not evaluated)
of one argument, say %3x. x %*is a list of pairs: %3((u%41%* v%41%*) ... (u%4n%* v%4n%*)).%1
Each %3u%4i%1 is the name of a function and each %3v%4i%1 is the λ-expression
definition.  Actually each %3u%4i%1 and %3v%4i%1 is the %2Sexpr translation%* of the
name and the function, but you knew that anyway.  The effect of %3define%*
is to put the appropriate definitions in the symbol table.

For example we might wish to define the function which reverses a list as:
%3
.BEGIN NOFILL;TURN OFF "←";
.GROUP

reverse <= λ[[x] prog[[y;z]
                       y ← x;
                       z ← NIL;
                     a [null[y] → return [z]];
                       z ← cons[car[y];z];
                       y ← cdr[y];
                       go[a];]]
%1
.APART

Then the following would make this definition grist for the %3evalquote%* mill.
.GROUP

%3
DEFINE((
        (REVERSE (LAMBDA (X)
                         (PROG (Y Z)
                           (SETQ Y X)
                           (SETQ Z NIL)
                         A(COND ((NULL Y)(RETURN Z)))
                           (SETQ Z (CONS (CAR Y) Z))
                           (SETQ Y (CDR Y))
                           (GO A) )))
                                       ))

%1
.APART
and subsequently:

%3REVERSE ((A B C))  %1would evaluate to: %3(C B A).%1

.END

%1
C. Weissman's LISP PRIMER is an excellent source of machine examples
and should be consulted now. Always remember that you are writing the sexpr representation
of LISP functions and expressions. Do not confuse the two.